home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / libwais / ir / sersrch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-03  |  15.4 KB  |  599 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.    
  4.    Brewster@think.com
  5. */
  6.  
  7.  
  8. /* implements the search part of irext.h 
  9.    (search_word and finished_search_word)
  10.    -brewster
  11.  
  12. Split from irsearch.c
  13.  
  14.    5/31/91 Added scale_scores.  Fixed document_score_array to long.
  15.    7/8/91 Removed scale_scores, handled in search_word with doc_id > 0.
  16.    2/4/92 Made document_score_array a double.
  17.  
  18.    - Jonny G
  19.  * $Log:    sersrch.c,v $
  20.  * Revision 1.24  92/04/28  16:56:54  morris
  21.  * added boolean to serial engine
  22.  * 
  23.  * Revision 1.23  92/03/15  10:15:18  jonathan
  24.  * Added Simon Spero's ASSIGN replacement for read_bytes.
  25.  * 
  26.  * Revision 1.22  92/03/05  07:09:54  shen
  27.  * add two more dummy arguments to call to init_search_engine
  28.  * 
  29.  * Revision 1.21  92/02/12  17:29:52  jonathan
  30.  * Conditionalized inclusion of object code.
  31.  * 
  32.  * Revision 1.20  92/02/12  13:40:06  jonathan
  33.  * Added "$Log" so RCS will put the log message in the header
  34.  * 
  35. */
  36.  
  37. #include "cdialect.h"
  38. #include "irfiles.h"
  39. #include "irsearch.h"
  40. #include "irext.h"
  41. #include "byte_order.h"
  42. #include <string.h>
  43.  
  44. #ifdef BOOL
  45. #include "obj.h"
  46. #include "irparse.h"
  47. object* currentQuery = NULL; /* kludge until irext goes away */
  48. #endif /* def BOOL */
  49.  
  50. /* weighting for relevant document terms - 
  51.    this may become a parameter to the query.
  52. */
  53.  
  54. #define RF_WEIGHTING 0.1
  55.  
  56. /* ==================================
  57.  * ===  Initialization Functions  ===
  58.  * ==================================*/
  59.  
  60.  
  61. long init_search_engine(file, initialize, for_search, cm_mem_percent, 
  62. text_size, grow_percent)
  63.   char* file;
  64.   boolean initialize;
  65.   boolean for_search;
  66.   long cm_mem_percent;  /* unused */
  67.   long text_size;     /* unused */
  68.   long grow_percent;  /* unused */
  69. {
  70.   static boolean inited = false;
  71.  
  72.   if (inited == false)
  73.    { 
  74. #ifdef BOOL
  75.      initObj();
  76.      initBool();
  77. #endif
  78.      inited = true;
  79.    }
  80.  
  81.   return(0);
  82. }
  83.  
  84. long finished_search_engine()
  85. {
  86.   return(0);
  87. }
  88.  
  89.  
  90. /*
  91.  *  ext_open_database: see irext.h
  92.  */
  93.  
  94. long ext_open_database (db, initialize, for_search)
  95.      database *db;
  96.      boolean initialize;
  97.      boolean for_search;
  98. { /* this has to deal with the .inv file */
  99.   char file[MAX_FILE_NAME_LEN];
  100.  
  101.   if(initialize) /* make a new one */
  102.     db->index_stream = s_fopen(index_filename(file, db), "w+b");
  103.   else if(for_search) /* just search */
  104.     db->index_stream = s_fopen(index_filename(file, db), "rb");
  105.   else /* write to an existing db */
  106.     db->index_stream = s_fopen(index_filename(file, db), "r+b");
  107.  
  108.   if (db->index_stream == NULL) {
  109.     waislog(WLOG_HIGH, WLOG_ERROR,"2can't open the inverted index file %s\n", 
  110.         file);
  111.       disposeDatabase(db);
  112.       return(1);
  113.     }
  114.   return(0);
  115. }
  116.   
  117.  
  118.  
  119. /*
  120.  *  ext_close_database: see irext.h
  121.  */
  122.  
  123. long ext_close_database (db)
  124.      database *db;
  125. {
  126.   return(0);
  127. }
  128.  
  129. char *database_file(database_name)
  130.      char *database_name;
  131. {
  132.   return(database_name);
  133. }
  134.   
  135. /*===========================*
  136.  *===  Setting Paramters  ===*
  137.  *===========================*/
  138.  
  139. long max_hit_retrieved = 0;
  140. char **srcs = NULL;
  141.  
  142. long set_query_parameter (mask, parameters)
  143.      long mask;
  144.      query_parameter_type * parameters;
  145. {
  146.   switch (mask)
  147.     {
  148.     case SET_MAX_RETRIEVED_MASK:
  149.       max_hit_retrieved = parameters->max_hit_retrieved;
  150.       return(0);
  151.       break;
  152.     case SET_SELECT_SOURCE:
  153.       if(NULL != srcs){
  154.     if(NULL != srcs[0])
  155.       s_free(srcs[0]);
  156.     s_free(srcs);
  157.       }
  158.       srcs = parameters->srcs;
  159.       break;
  160.     default:
  161.       return(-1);
  162.       break;
  163.     }
  164.   return(0);
  165. }
  166.  
  167. /*==============================*
  168.  *===  Document Score Array  ===*
  169.  *==============================*/
  170.  
  171. double *document_score_array = NULL;
  172. long document_score_array_len = 0;
  173.  
  174. /* make_document_score_array insures that the document_score_array
  175.    array is long enough, if not it makes it long enough */
  176. static void make_document_score_array _AP((long length));
  177. static void make_document_score_array(length)
  178. long length;
  179. {
  180.   if(length <= document_score_array_len)
  181.     return;
  182.   /* we have to make a new one.  free the old one first (if any) */
  183.   if(document_score_array != 0){
  184.     s_free(document_score_array);
  185.   }
  186.   document_score_array = (double*)s_malloc(
  187.                      (size_t)(length * sizeof(double)));
  188.   document_score_array_len = length;
  189. }
  190.  
  191. static void destroy_document_score_array _AP((void));
  192. static void destroy_document_score_array()
  193. {
  194.   s_free(document_score_array);
  195.   document_score_array_len = 0;
  196. }
  197.     
  198. void clear_document_score_array()
  199. /* side effects the document_score_array. */
  200. { 
  201.   memset(document_score_array, 0, 
  202.      document_score_array_len * sizeof(double));
  203. }
  204.  
  205. /* for debugging purposes */
  206. void print_document_score_array(start,stop)
  207. unsigned long start;
  208. unsigned long stop;
  209. /* assumes start >= 0, stop < db->doc_table_allocated_entries */
  210. {
  211.     long i;
  212.     for(i = start; i <= stop; i++){
  213.         printf("entry number %d: %f \n", 
  214.                i, document_score_array[i]);
  215.     }
  216. }
  217.  
  218.  
  219.  
  220. /*=========================*
  221.  *===  Best Hits Array  ===*
  222.  *=========================*/
  223.  
  224. hit *best_hits_array = NULL;
  225. long best_hits_array_len = 0;
  226. long current_best_hit = 0;
  227.  
  228. /* see irext.h for doc */
  229. long init_best_hit (db)
  230.      database *db;
  231. {
  232.  
  233. #ifdef BOOL
  234.   if (currentQuery != NULL)
  235.     send(currentQuery,InitBestHit,db);
  236. #endif /* def BOOL */
  237.  
  238.   return(0);
  239. }
  240.  
  241. /* make_best_hits_array insures that the best_hits_array
  242.    array is long enough, if not it makes it long enough */
  243. static void make_best_hits_array _AP((long length));
  244. static void make_best_hits_array(length)
  245. long length;
  246. {
  247.   if(length <= best_hits_array_len)
  248.     return;
  249.   /* we have to make a new one.  free the old one first (if any) */
  250.   if(best_hits_array != 0){
  251.     s_free(best_hits_array);
  252.   }
  253.   best_hits_array = (hit*)s_malloc((size_t)(length * sizeof(hit)));
  254.   best_hits_array_len = length;
  255. }
  256.  
  257. static void destroy_best_hits_array _AP((void));
  258. static void destroy_best_hits_array()
  259. {
  260.   s_free(best_hits_array);
  261.   best_hits_array_len = 0;
  262. }
  263.     
  264. void clear_best_hits_array()
  265. /* side effects the best_hits_array.  XXX could use memset */
  266. { 
  267.   memset((char*)best_hits_array, 0, best_hits_array_len * sizeof(hit));
  268. }
  269.  
  270. /* for debugging purposes */
  271. void print_best_hits()
  272. {
  273.   long i;
  274.   for( i = 0; i < best_hits_array_len; i++){
  275.     if (best_hits_array[i].weight != 0)
  276.       { printf("Best hit %ld: weight %ld, doc_id %ld, headline %s, filename %s, lines %ld\n", 
  277.            i, best_hits_array[i].weight, 
  278.            best_hits_array[i].document_id,
  279.            best_hits_array[i].headline,
  280.            best_hits_array[i].filename,
  281.            best_hits_array[i].number_of_lines);
  282.       }
  283.   }
  284. }
  285.  
  286. void sort_best_hits(db)
  287.      database * db;
  288. {
  289.   /* returns nothing.
  290.    * side effects best_hits and document_score_array
  291.    */
  292.  
  293.   long i, doc;
  294.   double worst_weight_to_make_it = 0.0;
  295.   document_table_entry doc_entry;
  296.   long best_hit_number = 0;
  297.  
  298.   /* snuff the scores */
  299.   for(i = 0; i < max_hit_retrieved; i++){
  300.     best_hits_array[i].weight = 0;
  301.   }
  302.  
  303.   /* loop over the doc, and keep the doc_id and weight in best hit table */
  304.   for(doc = 0; doc < db->doc_table_allocated_entries; doc++){
  305.     double weight = document_score_array[doc];
  306.     if(worst_weight_to_make_it < weight){
  307.       /* merge it into the best_hits array. start at the bottom */
  308.       for(i = (max_hit_retrieved - 1); i >= 0; i--){
  309.     if(weight > best_hits_array[i].weight 
  310.        /* && (check_document_id(doc, db) == true) too slow.*/
  311.        ){
  312.       /* move this entry down */    
  313.       if((i + 1) < max_hit_retrieved){
  314.         best_hits_array[i+1].weight = best_hits_array[i].weight;
  315.         best_hits_array[i+1].document_id = best_hits_array[i].document_id;
  316.       }
  317.       best_hits_array[i].document_id = doc;
  318.         best_hits_array[i].weight = weight;
  319.     }
  320.     else
  321.       break;
  322.       }      
  323.     }
  324.   }
  325.   
  326.   for(i = 0; i < max_hit_retrieved; i++){
  327.     if(best_hits_array[i].weight <= 0)  /* if we are out of good stuff, return */
  328.       return;
  329.     /* fill in the rest of the hit */
  330.     if (read_document_table_entry(&doc_entry,
  331.                   best_hits_array[i].document_id,
  332.                   db) 
  333.     == true){
  334.       best_hits_array[best_hit_number].weight = best_hits_array[i].weight;
  335.       best_hits_array[best_hit_number].document_id = best_hits_array[i].document_id;
  336.       best_hits_array[best_hit_number].start_character = doc_entry.start_character;
  337.       best_hits_array[best_hit_number].end_character = doc_entry.end_character;
  338.       best_hits_array[best_hit_number].document_length = doc_entry.document_length;
  339.       best_hits_array[best_hit_number].number_of_lines = doc_entry.number_of_lines;
  340.       read_filename_table_entry(doc_entry.filename_id, 
  341.                 best_hits_array[best_hit_number].filename,
  342.                 best_hits_array[best_hit_number].type,
  343.                 NULL,
  344.                 db),
  345.       strncpy(best_hits_array[best_hit_number].headline, 
  346.           read_headline_table_entry(doc_entry.headline_id,db),
  347.           MAX_FILE_NAME_LEN);
  348.       best_hit_number++;
  349.     } 
  350.     beFriendly();
  351.   }
  352.   for(i = best_hit_number; i < max_hit_retrieved; i++){
  353.     best_hits_array[best_hit_number].weight = 0;
  354.   }
  355.   /* print_best_hits(s);  for debugging */
  356. }
  357.  
  358.  
  359. /* returns the next best hit */
  360. long best_hit(db, doc_id, best_character, best_line, score)
  361.      database *db;
  362.      long *doc_id;    
  363.      long *best_character;
  364.      long *best_line;
  365.      long *score;
  366. {
  367.  
  368.   *best_character = 0; 
  369.   *best_line = 0;
  370.   
  371. #ifdef BOOL
  372.   if (currentQuery != NULL) /* for boolean */
  373.    {
  374.      send(currentQuery,GetBestHit,db,doc_id,best_character,best_line,score);
  375.      if (*doc_id > 0)
  376.        return(0); /* ok */
  377.      else
  378.        return(-1); /* no more docs */
  379.    }
  380. #endif /* BOOL */
  381.  
  382.   if(current_best_hit > best_hits_array_len)
  383.     return(1);
  384.   if(best_hits_array[current_best_hit].weight == 0)
  385.     return(1);
  386.   *doc_id = best_hits_array[current_best_hit].document_id;
  387.   *score  = best_hits_array[current_best_hit].weight;
  388.   current_best_hit++;
  389.   return(0);
  390. }
  391.  
  392. long finished_best_hit(db)
  393. database *db;
  394. { 
  395.  
  396. #ifdef BOOL
  397.   if (currentQuery != NULL) /* for boolean */
  398.    { send(currentQuery,Delete);
  399.      currentQuery = NULL;
  400.      return(0);
  401.    }
  402. #endif /* BOOL */
  403.  
  404.   /* if we are on a small machine, we might want to 
  405.      destroy_document_score_array */
  406.   clear_document_score_array();
  407.   clear_best_hits_array();
  408.   current_best_hit = 0;
  409.   return(0);
  410. }
  411.  
  412. /*=============================*    
  413.  *===  Searching for words  ===*
  414.  *=============================*/
  415.  
  416. /* see irext.h for doc */
  417. long init_search_word (db)
  418.      database* db;
  419. {
  420.   return(0);
  421. }
  422.  
  423. /* see irext.h for doc */
  424. long search_word(word,char_pos, line_pos, weight, doc_id, 
  425.          word_pair, db)
  426.      char *word; /* the word to be searched for */
  427.      long char_pos;        /* the position of the start of the word */
  428.      long line_pos;        /* is this needed? not for signature system */
  429.      long weight;        /* how important the word looks syntactically,
  430.                    such as is it bold */
  431.      long doc_id;        /* current document, seed words is 0,
  432.                    then it increments into the relevant 
  433.                    document */
  434.      long word_pair;
  435.      database *db;
  436. {
  437.   /* this side effects the document_score_array,
  438.    * and downcases the word.
  439.    * Returns 0 if successful or word not present, 
  440.    * returns non-0 if an error.
  441.    *
  442.    */
  443.   
  444.   long not_full_flag = INDEX_BLOCK_FULL_FLAG; /*start out full so it will go on looking */
  445.   long count, index_block_size;
  446.   long internal_document_id, internal_weight, number_of_valid_entries;
  447.   long index_file_block_number;
  448.   long number_of_occurances;
  449.  
  450.   FOUR_BYTE index_buffer_data[INDEX_ELEMENT_SIZE*(1024/4)];
  451.   char *index_buffer;
  452.   char *i;
  453.   FILE *stream = NULL;
  454.  
  455.   index_buffer = (char*)index_buffer_data;
  456.  
  457.   index_file_block_number = 
  458.     look_up_word_in_dictionary(word, &number_of_occurances, db);
  459.  
  460.   current_best_hit = 0;  /* so that the best hits willstart from 0 */
  461.  
  462.   /* check the document_score_array */
  463.   if(document_score_array_len < db->doc_table_allocated_entries)
  464.     make_document_score_array(db->doc_table_allocated_entries);
  465.  
  466.   if(index_file_block_number >= 0){
  467.     stream = db->index_stream;
  468.     
  469.     while((not_full_flag != INDEX_BLOCK_NOT_FULL_FLAG) && 
  470.       (index_file_block_number != 0)){    
  471.       /* read the index block */
  472.       if (0 != fseek(stream, (long)index_file_block_number, 
  473.              SEEK_SET))    
  474.     { 
  475.       waislog(WLOG_HIGH, WLOG_ERROR, 
  476.           "fseek failed into the inverted file to position %ld",
  477.           (long)index_file_block_number); 
  478.       return(-1);
  479.     }
  480.       
  481.       read(fileno(stream),index_buffer,INDEX_BLOCK_HEADER_SIZE);
  482.  
  483.       ASSIGN(not_full_flag,
  484.          INDEX_BLOCK_FLAG_SIZE,
  485.          index_buffer,
  486.          INDEX_BLOCK_HEADER_SIZE,
  487.          0 );
  488.       ASSIGN(index_file_block_number,NEXT_INDEX_BLOCK_SIZE,
  489.          index_buffer+INDEX_BLOCK_FLAG_SIZE,
  490.          INDEX_BLOCK_HEADER_SIZE,
  491.          INDEX_BLOCK_FLAG_SIZE);
  492.       ASSIGN(index_block_size,INDEX_BLOCK_SIZE_SIZE,
  493.          index_buffer+INDEX_BLOCK_FLAG_SIZE+NEXT_INDEX_BLOCK_SIZE,
  494.          INDEX_BLOCK_HEADER_SIZE,
  495.          INDEX_BLOCK_FLAG_SIZE+NEXT_INDEX_BLOCK_SIZE);
  496.  
  497. /* 
  498.   this is equivalent, but slower:
  499.       not_full_flag = read_bytes(INDEX_BLOCK_FLAG_SIZE, stream);
  500.       index_file_block_number = read_bytes(NEXT_INDEX_BLOCK_SIZE, stream);
  501.       index_block_size = read_bytes(INDEX_BLOCK_SIZE_SIZE, stream);
  502.  
  503.       printf("flag = %d, block_num = %d, block_size = %d\n",
  504.          not_full_flag, 
  505.          index_file_block_number,
  506.          index_block_size);
  507.  
  508.       fflush(stdout);
  509. */
  510.       if(EOF == index_block_size) 
  511.     { 
  512.       waislog(WLOG_HIGH, WLOG_ERROR, 
  513.           "reading from the index file failed");
  514.       return(-1);
  515.     }
  516.       
  517.       if(not_full_flag == INDEX_BLOCK_NOT_FULL_FLAG){
  518.     /* not full */
  519.     number_of_valid_entries = index_file_block_number;
  520.       }
  521.       else if(not_full_flag == INDEX_BLOCK_FULL_FLAG){
  522.     /* full */
  523.     number_of_valid_entries = index_block_size - INDEX_BLOCK_HEADER_SIZE;
  524.       }
  525.       else{            /* bad news, file is corrupted. */
  526.     waislog(WLOG_HIGH, WLOG_ERROR, 
  527.         "Expected the flag in the inverted file to be valid.  it is %ld",
  528.         not_full_flag);
  529.     return(-1);
  530.       }
  531.       /* printf("number of valid bytes: %ld\n", number_of_valid_entries); */
  532.       
  533.       /* add the array to the document_score_array */
  534.       number_of_valid_entries /= INDEX_ELEMENT_SIZE;
  535.  
  536.       for(count=0;count <  number_of_valid_entries;count++) {
  537.     int wgt;
  538.     int did;
  539.     if(count%1024 == 0) {
  540.       read(fileno(stream),index_buffer,INDEX_ELEMENT_SIZE*
  541.         MIN(1024,number_of_valid_entries-count));
  542.       i=index_buffer;
  543.     }
  544.     ASSIGN(wgt,WEIGHT_SIZE,    
  545.            i+DOCUMENT_ID_SIZE+WORD_POSITION_SIZE+CHARACTER_POSITION_SIZE,
  546.            INDEX_ELEMENT_SIZE,
  547.            DOCUMENT_ID_SIZE+WORD_POSITION_SIZE+CHARACTER_POSITION_SIZE);
  548.     ASSIGN(did,DOCUMENT_ID_SIZE,i,INDEX_ELEMENT_SIZE,0);
  549.  
  550.     internal_weight = wgt;
  551.     internal_document_id = did;
  552.  
  553.     /*
  554.     printf("entry %ld, Doc_id: %ld, weight %ld \n",
  555.         count, internal_document_id, internal_weight);
  556.     fflush(stdout);
  557.     */
  558.     if(EOF == internal_weight) 
  559.       { 
  560.         waislog(WLOG_HIGH, WLOG_ERROR, 
  561.             "reading from the doc-id table failed");
  562.         return(-1);
  563.       }
  564.     /* if(doc_id > 0) we are doing a relevant document */
  565.     document_score_array[internal_document_id] += 
  566.       (doc_id) ? (internal_weight * RF_WEIGHTING) : internal_weight;
  567.     i+=INDEX_ELEMENT_SIZE;
  568.       }
  569.     }
  570.     return(0); 
  571.   }
  572.   else if(0 == index_file_block_number){
  573.     /* an error occurred on looking up the word */
  574.     return(-1);
  575.   }
  576.   else                /* index_file_block_number is negative */
  577.     return(0);        /* word not present */
  578. }
  579.  
  580. /* now collect the best hits */
  581. long finished_search_word(db)
  582.      database *db;
  583. { 
  584.  
  585. #ifdef BOOL
  586.   if (currentQuery != NULL)
  587.     return; /* do nothing for boolean */
  588. #endif /* def BOOL */
  589.  
  590.   /* check the document_score_array */
  591.   if(document_score_array_len < db->doc_table_allocated_entries)
  592.     make_document_score_array(db->doc_table_allocated_entries);
  593.  
  594.   make_best_hits_array(max_hit_retrieved);
  595.   sort_best_hits(db);
  596.   return(0);
  597. }
  598.  
  599.